// https://leetcode.cn/problems/flatten-binary-tree-to-linked-list/?envType=study-plan-v2&envId=top-100-liked

// 算法思路总结：
// 1. 前序遍历递归展开二叉树为链表
// 2. 使用prev指针记录前一个访问的节点
// 3. 将当前节点连接到prev的右子树，左子树置空
// 4. 递归处理左右子树，注意保存原始指针
// 5. 时间复杂度：O(n)，空间复杂度：O(h)

#include <iostream>
using namespace std;

#include <vector>
#include <string>
#include <algorithm>
#include "BinaryTreeUtils.h"

class Solution 
{
public:
    void flatten(TreeNode* root) 
    {
        TreeNode* prev = nullptr;

        recur(root, prev);

        return ;
    }

    void recur(TreeNode* root, TreeNode*& prev)
    {
        if (root == nullptr)
        {
            return ;
        }

        TreeNode* left = root->left;
        TreeNode* right = root->right;

        if (prev != nullptr)
        {
            prev->left = nullptr;
            prev->right = root;    
        }
        prev = root;

        recur(left, prev);
        recur(right, prev);

        return ;
    }
};

int main()
{
    vector<string> nodes1 = {"1","2","5","3","4","null","6"};
    vector<string> nodes2 = {"0"};

    Solution sol;

    auto root1 = buildTree(nodes1);
    auto root2 = buildTree(nodes2);

    sol.flatten(root1);
    sol.flatten(root2);

    printTree(root1);
    printTree(root2);

    return 0;
}